package recursion


func GetMaxValue(w []int, v[]int, bag int) int {
	return KnapsackProcess(w, v, 0, 0, bag, 0)
}

func KnapsackProcess(w []int, v[]int, index int, alReadyWeight int, bag int, value int) int {
	if index == len(w) {
		if alReadyWeight == bag {
			return value
		}
		if alReadyWeight > bag {
			return -1
		}
		return value
	}
	p1 := KnapsackProcess(w, v, index+1, alReadyWeight, bag, value)
	p2 := -1
	p2 = KnapsackProcess(w, v, index+1, alReadyWeight+w[index], bag, value+v[index])
	if p2 != -1 {
		return max(p1, p2)
	}
	return p1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func GetMaxValue1(w []int, v[]int, bag int) int {
	return KnapsackProcess1(w, v, 0, 0, bag)
}

func KnapsackProcess1(w []int, v[]int, index int, alReadyWeight int, bag int) int {
	if alReadyWeight > bag {
		return -1
	}
	if index == len(w) {
		return 0
	}
	p1 := KnapsackProcess1(w, v, index+1, alReadyWeight, bag)
	p2Next := KnapsackProcess1(w, v, index+1, alReadyWeight+w[index], bag)
	p2 := -1
	if p2Next != -1 {
		p2 = v[index] + p2Next
	}
	return max(p1, p2)
}

func GetMaxValue3(w []int, v[]int, bag int) int {
	return KnapsackProcess3(w, v, 0, bag, bag)
}

func KnapsackProcess3(w []int, v[]int, index int, rest int, bag int) int {
	if rest < 0 {
		return -1
	}
	if index == len(w) {
		return 0
	}
	p1 := KnapsackProcess3(w, v, index+1, rest, bag)
	p2Next := KnapsackProcess3(w, v, index+1, rest-w[index], bag)
	p2 := -1
	if p2Next != -1 {
		p2 = v[index] + p2Next
	}
	return max(p1, p2)
}


func GetMaxValueDp(w []int, v[]int, bag int) int {
	dp := make([][]int, len(w)+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, bag+1)
	}
	for i:=0; i<=bag; i++ {
		dp[len(w)][i] = 0
	}

	for index:=len(w)-1; index>=0; index-- {
		for rest:=0; rest<=bag; rest++ {
			p1 := dp[index+1][rest]
			p2 := -1
			if rest-w[index] >= 0 {
				p2 = dp[index+1][rest-w[index]] + v[index]
			}
			dp[index][rest] = max(p1, p2)
		}
	}
	return dp[0][bag]
}